<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>

    <script>
        console.log('====链表求和两数之和====')
        function ListNode(val, next) {
            this.val = (val === undefined ? 0 : val)
            this.next = (next === undefined ? null : next)
        }
        let head = new ListNode(1);
        var addTwoNumbers = function (l1, l2) {
            let dummy = new ListNode(0); // 哑节点简化操作
            let current = dummy;
            let carry = 0;

            while (l1 || l2 || carry) {
                // 获取当前位的值（若链表已结束则用0代替）
                const val1 = l1 ? l1.val : 0;
                const val2 = l2 ? l2.val : 0;

                // 计算当前位总和及进位
                const sum = val1 + val2 + carry;
                carry = Math.floor(sum / 10);
                // 创建新节点并移动指针
                current.next = new ListNode(sum % 10);
                current = current.next;
                // 移动链表指针
                if (l1) l1 = l1.next;
                if (l2) l2 = l2.next;
            }

            return dummy.next;
        };

        const l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
        const l2 = new ListNode(5, new ListNode(6, new ListNode(4)));
        console.log("链表求和两数之和为:", addTwoNumbers(l1, l2));

        console.log('====无重复字符的最长子串====')
        function lengthOfLongestSubstring(s) {
            let maxLength = 0;
            let start = 0;
            let charIndexMap = {};

            for (let i = 0; i < s.length; i++) {
                if (charIndexMap[s[i]] !== undefined) {
                    start = Math.max(start, charIndexMap[s[i]] + 1);
                }
                charIndexMap[s[i]] = i;
                maxLength = Math.max(maxLength, i - start + 1);
            }
            return maxLength;

        };
        console.log("无重复字符的最长子串长度为:", lengthOfLongestSubstring("abcabcbb")); // 3


        console.log('====合并数组取中位数====')
        function findMedianSortedArrays(nums1, nums2) {
            const newArray = [...nums1, ...nums2].sort((a, b) => a - b);
            const mid = Math.floor(newArray.length / 2);
            if (newArray.length % 2 === 0) {
                return (newArray[mid - 1] + newArray[mid]) / 2;
            } else {
                return newArray[mid];
            }
        }
        console.log("合并数组取中位数为:", findMedianSortedArrays([1, 3], [2])); // 2.0

        console.log('====最长回文====')
        function longestPalindrome(s) {
            if (s.length < 2) {
                return s;
            }
            let start = 0, maxLength = 1;
            function expandAroundCenter(left, right) {

                while (left >= 0 && right < s.length && s[left] === s[right]) {
                    const currentLength = right - left + 1;
                    if (currentLength > maxLength) {
                        start = left;
                        maxLength = currentLength;
                    }
                    left--;
                    right++;
                }
            }
            for (let i = 0; i < s.length; i++) {
                expandAroundCenter(i, i);
                expandAroundCenter(i, i + 1);
            }
            return s.substring(start, start + maxLength);
        }
        console.log("最长回文为:", longestPalindrome("baab")); // "bab"

        console.log('====解析字符串并按照给定的行数将其转化为Z字形排列的字符串====')
        const aa = "PAYPALISHIRING"
        function convert(aa, newRows) {
            let rows = Array(newRows).fill('');
            let curRow = 0;
            // 用于判断当前行是否需要向下移动
            let goingDown = false;

            for (let i = 0; i < aa.length; i++) {
                rows[curRow] += aa[i];
                // 到达顶端或底端时改变方向
                if (curRow === 0 || curRow === newRows - 1) {
                    goingDown = !goingDown;
                }
                curRow += goingDown ? 1 : -1;
            }
            return rows.join('');
        }

        console.log('====通用回文判断函数====')
        var isPalindrome = function (x) {
            const str = String(x);
            let left = 0, right = str.length - 1;
            while (left < right) {
                if (str[left] !== str[right]) {
                    return false;
                }
                left++;
                right--;
            }
            return true;
        };
        console.log(isPalindrome(-121));

        console.log('====盛最多水的容器====')
        var maxArea = function (height) {
            let left = 0, right = height.length - 1;
            const arr = [];
            while (left < right) {
                if (left >= right) {
                    break;
                }
                const area = Math.min(height[left], height[right]) * (right - left);
                arr.push(area);

                if (height[left] > height[right]) {
                    right--;
                } else {
                    left++;
                }
            }
            return Math.max(...arr);
        };
        console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]));
        console.log(maxArea([1, 1]));


        // 整数转罗马数字
        console.log('====整数转罗马数字====');
        var intToRoman = function (num) {
            const hashMap = {
                1: 'I',
                4: 'IV',
                5: 'V',
                9: 'IX',
                10: 'X',
                40: 'XL',
                50: 'L',
                90: 'XC',
                100: 'C',
                400: 'CD',
                500: 'D',
                900: 'CM',
                1000: 'M'
            }
            let res = '';
            function getMinKey() {
                const arr = [];
                for (let k in hashMap) {
                    let count = num / k;
                    if (count >= 1) {
                        arr.push({
                            key: k,
                            count: count
                        })
                    }
                };

                arr.sort((a, b) => a.count - b.count);
                return arr[0];
            }
            while (num > 0) {
                const obj = getMinKey();
                const count = Math.floor(obj.count);
                res += hashMap[obj.key].repeat(count);
                num = num % (Number(obj.key) * count);
                console.log(num);

            }
            return res;
        };

        console.log(intToRoman(3749)); // "MMMDCCXLIX"

        console.log('====最长公共前缀====');
        var longestCommonPrefix = function (strs) {
            let prefix = strs[0];
            for (let i = 1; i < strs.length; i++) {
                while (strs[i].indexOf(prefix) !== 0) {
                    prefix = prefix.substring(0, prefix.length - 1);
                    if (prefix === "") return "";
                }
            }
            return prefix;
        };
        console.log(longestCommonPrefix(["flower", "flow", "flight"])); // "fl"
    </script>
</body>

</html>